"""
https://leetcode.cn/problems/maximum-product-subarray/description/

152. 乘积最大子数组
已解答
中等
相关标签
相关企业
给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续 子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

测试用例的答案是一个 32-位 整数。

 

示例 1:

输入: nums = [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
示例 2:

输入: nums = [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
 

提示:

1 <= nums.length <= 2 * 104
-10 <= nums[i] <= 10
nums 的任何子数组的乘积都 保证 是一个 32-位 整数

"""

from typing import List


class Solution:
    """
    看题目涉及数组，有数个分散的结果，但最后求一个值，各个子数组之间可能有互相计算，大概率是dp解法。
    实际主要处理的是负号问题。向前遍历直到0出现，维护一个负值乘积，一个正值乘积。

    -1 2 -3 4 -5 -6 7

    dpp[i]表示以第i个元素结尾的最大乘积,dpn[i]表示最小乘积（通常是负数）
    则dpp[0]=dpn[0]=nums[0]
    i>0时：
    if nums[i]==0:
        dpp[i]=dpn[i]=0
    if nums[i-1]==0: # dpp[i-1]=dpn[i-1]=0
        dpp[i]=dpn[i]=nums[i]
    else: # dpp[i-1]!=0 dpn[i-1]!=0
        if nums[i]>0:
            dpp[i]=dpp[i-1]*nums[i] if dpp[i-1]>1 else nums[i]
            dpn[i]=dpn[i-1]*nums[i] if dpn[i-1]<0 else nums[i]
        else:
            dpp[i]=dpn[i-1]*nums[i] if dpn[i-1]<0 else nums[i]
            dpn[i]=dpp[i-1]*nums[i] if dpp[i-1]>1 else nums[i]



    """

    def maxProduct(self, nums: List[int]) -> int:
        dpp=[0]*len(nums)
        dpn=[0]*len(nums)

        dpp[0]=dpn[0]=nums[0]
        global_max=nums[0]
        for i in range(1,len(nums)):
            if nums[i-1]==0:
                dpp[i]=dpn[i]=nums[i]
            elif nums[i]>0:
                dpp[i]=dpp[i-1]*nums[i] if dpp[i-1]>1 else nums[i]
                dpn[i]=dpn[i-1]*nums[i] if dpn[i-1]<0 else nums[i]
            elif nums[i]<0:
                dpp[i]=dpn[i-1]*nums[i] if dpn[i-1]<0 else nums[i]
                dpn[i]=dpp[i-1]*nums[i] if dpp[i-1]>1 else nums[i]
            
            global_max=max(global_max,dpp[i])
        # print(dpp,dpn)
        return global_max

if __name__ =='__main__':
    nums=[-2,0,-1]

    sol=Solution()
    res=sol.maxProduct(nums)
    print(res)